In “How to Share a Secret”, A. Shamir, Communications of the ACM, vol. 22, pp. 612-613, 1979 (Shamir) there is described a method whereby, given two numbers n and m, where m<n, an arbitrary secret can be split into n parts (shares), such that any m of the resulting shares can be combined to recover the original secret. The technique ensures that anyone who has less than m shares is no better off than if they had no shares at all. This technique also allows the sharing of a secret such that any m of n shareholders can reconstruct the secret without revealing their shares.
Referring now to FIG. 1, which illustrates the principles involved in more detail, there is shown a pair of cubic graphs based on the formula:y=ax3+bx2+cx+d 
Conventionally, the y value at x=0 is taken to be a secret, and shares in the secret, comprising values from which other y values can be derived, are distributed across n share-holders, in this case n=6, typically servers with which a client computer can connect securely. Using simultaneous equations it will be seen that given any four points, say (x1,y1); (x2,y2); (x3,y3) and (x4,y4) on a curve, then any other point on the curve including the secret can be determined—so here m=4.
In, “Server-Assisted Generation of a Strong Secret from a Password”, W. Ford and B. Kaliski, Proceedings of the IEEE 9th International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, NIST, Gaithersburg Md., Jun. 14-16, 2000 (Ford-Kaliski) which in turn refines “Strong Password-Only Authenticated Key Exchange”, D. Jablon, Computer Communication Review, ACM SIGCOMM, vol. 26, no. 5, pp. 5-26, October 1996 (Jablon) there is disclosed a technique (SPEKE) for securely retrieving a number from, for example, a remote server without revealing a password to the remove server.
So, referring to FIG. 2, using Ford-Kaliski in combination with Shamir, a user running an application 12 on a client machine 10 on which they do not want to store, for example, their private key can store their private key in an encrypted format on a remote credentials storing server 20. The private key is encrypted with a secret number generated from shares comprising arbitrary numbers yi stored on share-holding servers B1 . . . Bn.
Using Ford-Kaliski, once a secret has been constructed by a secret generation component 14, the user can supply their password to the application on the client machine and a secret re-construction component 16 of the application connects to all n servers and without disclosing the password, securely obtains m shares yi. Points (xi) on a curve, for example a curve of the type shown in FIG. 1, are calculated from the formula xi=gyi mod p, where g is a hash version of the password and p is 1024-bit prime number. From these points, the secret value at x=0 can be determined. The encrypted private key can then be downloaded from the credentials server and decrypted with the secret value, to enable the user of the client to securely communicate with other users or to properly authenticate themselves to other devices on a network 30 such as a LAN, Intranet or Internet. So, for example, the system can be employed by “hot-desking” bank tellers who regularly use different computer terminals in a bank branch and whose access to bank records must be both secure and/or authenticated.
It can be seen from FIG. 1 that in an m-of-n system more shares than are necessary to re-generate a secret can be stored on servers so providing redundancy in the case of a communication failure with up to n-m of the servers. However, in order for a secret update component 18 to change the secret, it must not only be able to re-generate the secrete but also be able to change the values of all shares of the secret.
Many patents reference Shamir, and largely fall into one of a number of categories:
Patents which reference Shamir's paper, but do not make use of secret sharing techniques:
U.S. Pat. No. 5,553,145; U.S. Pat. No. 5,629,982; U.S. Pat. No. 5,666,420; U.S. Pat. No. 6,134,326; U.S. Pat. No. 6,137,884; and U.S. Pat. No. 6,141,750: Simultaneous electronic transactions with subscriber verification;
U.S. Pat. No. 5,812,670: Traceable anonymous transactions; and
U.S. Pat. No. 6,055,508: Method for secure accounting and auditing on a communications network.
Patents which disclose secret sharing for fault-tolerant transmission:
U.S. Pat. No. 5,485,474: Scheme for information dispersal and reconstruction; and
U.S. Pat. No. 6,012,159: Method and system for error-free data transfer.
Patents which disclose secret-sharing techniques, where the secret is not updated, as in:
U.S. Pat. No. 5,315,658; U.S. RE036,918: Fair cryptosystems and methods of use;
U.S. Pat. No. 5,495,532: Secure electronic voting using partially compatible homomorphisms;
U.S. Pat. No. 5,666,414: Guaranteed partial key-escrow;
U.S. Pat. No. 5,708,714: Method for sharing secret information and performing certification in a communication system that has a plurality of information processing apparatus;
U.S. Pat. No. 5,768,388: Time delayed key escrow;
U.S. Pat. No. 5,825,880: Multi-step digital signature method and system;
U.S. Pat. No. 5,903,649: Method for establishing a common code for authorized persons through a central office;
U.S. Pat. No. 5,991,414: Method and apparatus for the secure distributed storage and retrieval of information;
U.S. Pat. No. 6,192,472: Method and apparatus for the secure distributed storage and retrieval of information; and
U.S. Pat. No. 6,026,163: Distributed split-key cryptosystem and applications.
Miscellaneous patents, such as:
U.S. Pat. No. 5,764,767: System for reconstruction of a secret shared by a plurality of participants, which provides a mechanism for updating a shared secret, however, all the locations where the secrets are stored are active participants in updating the secret;U.S. Pat. No. 5,867,578: Adaptive multi-step digital signature system and method of operation thereof, where the shares change but the value of the shared secret is maintained; andU.S. Pat. No. 6,122,742: Auto-recoverable and auto-certifiable cryptosystem with unescrowed signing keys, which uses a shared function, not a shared secret.
Pieprzyk discloses a method of constructing shares in a secret k comprising the steps of: determining n shares for an n-of-n secret sharing scheme, each share comprising a value y; storing at least some of said shares in computing devices such that at least m of said n shares are reliably accessible; and determining the shared secret k according to said shares y.
It will be seen, however, that none of these documents discloses being able to update a shared secret without having access to all the shareholders of the secret. This becomes an important requirement when clients such as that shown in FIG. 2 are accessing shareholder servers across unreliable links such as network links or communication links or links through which bandwidth may need to be regulated by, for example, a load-balancing server (not shown) which may prevent or unduly delay a client's access to a shareholder server.